Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization

摘要

In this paper, we consider two paradigms that are developed to account foruncertainty in optimization models: robust optimization (RO) and jointestimation-optimization (JEO). We examine recent developments on efficient andscalable iterative first-order methods for these problems, and show that theseiterative methods can be viewed through the lens of online convex optimization(OCO). The standard OCO framework has seen much success for its ability tohandle decision-making in dynamic, uncertain, and even adversarialenvironments. Nevertheless, our applications of interest present furtherflexibility in OCO via three simple modifications to standard OCO assumptions:we introduce two new concepts of weighted regret and online saddle pointproblems and study the possibility of making lookahead (anticipatory)decisions. Our analyses demonstrate that these flexibilities introduced intothe OCO framework have significant consequences whenever they are applicable.For example, in the strongly convex case, minimizing unweighted regret has aproven optimal bound of $O(\log(T)/T)$, whereas we show that a bound of$O(1/T)$ is possible when we consider weighted regret. Similarly, for thesmooth case, considering $1$-lookahead decisions results in a $O(1/T)$ bound,compared to $O(1/\sqrt{T})$ in the standard OCO setting. Consequently, theseOCO tools are instrumental in exploiting structural properties of functions andresulting in improved convergence rates for RO and JEO. In certain cases, ourresults for RO and JEO match the best known or optimal rates in thecorresponding problem classes without data uncertainty.